package com.duoduo.链表;

import com.duoduo.ListNode;

/**
 * @author dl.chai
 * @version 1.0
 * @description: 排序链表148
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 * @date 2023/3/17 10:37
 */

public class 排序链表148 {
    public ListNode sortList(ListNode head) {
        /*
        链表的的归并排序
        1.排序使得两边的节点各自有序
        2.合并两个有序链表
         */
        if (head == null || head.next == null) {
            return head;
        }
        // 利用快慢指针找到中间的节点
        ListNode slow = head, fast = head, slowPre = null;
        while (fast != null && fast.next != null) {
            slowPre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode next;   // 后面部分的头结点
        // slow停留位置：奇数个走到中间，偶数个在中间偏右
        if (fast == null) {
            // 偶数
            next = slow;
            slowPre.next = null;    // 切断
        } else {
            // 奇数
            next = slow.next;
            slow.next = null;   // 断开
        }
        // 排序左右边的链表并记录头结点
        ListNode node1 = sortList(head);
        ListNode node2 = sortList(next);
        // 合并两个有序链表
        ListNode dummy = new ListNode(0), cur = dummy;
        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val) {
                cur.next = node1;
                node1 = node1.next;
            } else {
                cur.next = node2;
                node2 = node2.next;
            }
            cur = cur.next;
        }
        // 还有的节点没有走完
        while (node1 != null) {
            cur.next = node1;
            node1 = node1.next;
            cur = cur.next;
        }
        while (node2 != null) {
            cur.next = node2;
            node2 = node2.next;
            cur = cur.next;
        }
        // 返回合并后新的头结点
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode root = new ListNode(4);
        root.next = new ListNode(2);
        root.next.next = new ListNode(1);
        root.next.next.next = new ListNode(3);
        ListNode node = new 排序链表148().sortList(root);
        System.out.println(node);

    }
}
